package BFS;

import org.junit.Test;

import java.util.*;

/**
 * 最短路径 广搜
 *
 * 按 lbld 标准模版 走
 *
 * 先 写完全面向过程代码，
 * 再 ctrl+x 拆子函数，[ 复制多份相同代码 稳 ]
 */
public class 打开转盘锁752 {

    public int openLock(String[] deadends, String target)  {
        if(target.equals("0000")) return 0;
        List<String> deadEndsList = Arrays.asList(deadends);

        int minStep = 0;
        // 容器
        Queue<String> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        // root
        q.offer("0000");
        vis.add("0000");

        while(!q.isEmpty()) {
            // oldSize
            int oldSize = q.size();
            System.out.println(oldSize);

            for (int i = 0; i < oldSize; i++) {
                // * 判断cur
                String cur = q.poll();
                if(deadEndsList.contains(cur)) continue;
                if(cur.equals(target)) return minStep;
                // 只+周围 ( vis 只在这里用 )
                for (int j = 0; j < 4; j++) {
                    addUpAndDownAtThisIndex(cur, j, q, vis);
                }
            }
            minStep++;
        }
        return -1; // 无解
    }

    private void addUpAndDownAtThisIndex(String cur, int j, Queue<String> q, Set<String> vis) {
        char[] chars = cur.toCharArray();
        if (chars[j] == '0')
            ZeroHandler(chars,vis, j, q);
        else if (chars[j] == '9')
            NineHandler(chars,vis,j,q);
        else
            OtherHandler(chars,vis,j,q);
    }
    void ZeroHandler(char[] chars, Set<String> vis, int j, Queue<String> q){
        chars[j] = '1';
        String newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }

        chars[j] = '9';
        newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }
    }
    void NineHandler(char[] chars, Set<String> vis, int j, Queue<String> q){
        chars[j] = '0';
        String newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }

        chars[j] = '8';
        newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }
    }
    void OtherHandler(char[] chars, Set<String> vis, int j, Queue<String> q){
        chars[j] += 1;
        String newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }

        chars[j] -= 2; // 错：-2 不是 -1，因为上面有+1
        newStr = new String(chars);
        if(!vis.contains(newStr)) {
            q.add(newStr);
            vis.add(newStr);
        }
    }

    @Test
    public void test(){
        String[] s = new String[5];
        s[0] = "2002";
        s[1] = "0201";
        s[2] = "0101";
        s[3] = "0102";
        s[4] = "1212";
        System.out.println(openLock(s, "0202"));
    }
}
